1. Field of the Invention
The present invention generally relates to distributed processing and more particularly, the present invention relates to encouraging computer participation in distributed processing.
2. Background Description
A complex computer program may be segmented into multiple smaller manageable tasks. The tasks then may be distributed amongst a group of individual computers for independent completion. When a large computer program is partitioned or segmented into modular components and the segmented components are distributed over two or more machines, this is known as distributed processing. Other situations in which a computational task is distributed among several processors may include searching through a large search space (e.g., all subsets of some set of objects) and massive database searches. In such situations, the same program may run on different processors or computers using different inputs. Component placement can have a significant impact on program performance. Therefore, efficiently managing distributed programs and distributed computational tasks is a major challenge, especially when components are distributed over a network to remotely located connected computers, e.g., to computers connected together over the Internet.
A fundamental problem facing distributed application developers is application partitioning and component or object placement. Typically, ad hoc heuristics or other distributed processing models are used to get to some solution that may be very far from the optimum. Problems also arise in component or object scheduling and packing. The economic significance of distributed processing is enormous due to potentially better utilization of human resources and reduction in costly computer hardware purchases.
Many such distributed processing optimization problems involve searches that are conducted in a very large space of N possible solutions. The optimization difficulty is due to the enormous number of possible solutions that must be examined to identify the best solution. Optimization algorithms and search methods have been developed over the past several years that have been successful in solving problems of increasing size, but the size of the problems keeps increasing; So, no matter how much improvement is seen in these algorithms and methods, there is always a need for better solution methods. The primary objective of these approaches is to reduce the program time to completion, as is further described hereinbelow.
Some state-of-the-art search methods derive a significant benefit from increasing the number of processors (P) working in parallel on the same problem, by dividing the problem and sharing the computational requirement amongst the processors. Thus, a brute-force search of the N possible solutions can be sped up by a factor of P, the number of processors employed. So, a problem that might take 30 years to solve on a single machine could be done in a single day by partitioning the problem into 10,000 segments of equal size and allocating each of the segments to one of 10,000 machines.
One approach to these large processing problems is to use parallel computing machines. The recently announced Blue Gene architecture from International Business Machines (IBM) Corporation is projected to incorporate one million processors within a single machine but, may take several years of development. In addition, the cost of such a machine will be prohibitive for most businesses. Consequently, these parallel computer machines still do not provide a realistic solution for large multi-solution searches.
Another approach is, simply, to distribute the 10,000 segments to 10,000 individual machines. With this approach, communication between processors is currently the main problem. However, in search related problems interprocessor communication is not a critical issue. The search machines do not even interact with each other until each one finds a best solution in its “territory.”
Even so, acquiring and maintaining 10,000 machines is not a trivial task. Also, since hardware costs keep falling, purchasing a large number of computers is a losing investment. Furthermore, maintaining such a volume of hardware requires retaining human resources that are also typically very expensive. So, it is impractical for a single business to allocate the resources to purchase and maintain more than 10,000 parallel machines to solve large search problems that may arise only infrequently.
For an example of another approach, see U.S. Pat. No. 6,112,225 entitled “Task Distribution Processing System and the Method for Subscribing Computers to Perform Computing Tasks During Idle Time” to Kraft et al., assigned to the assignee of the present invention and incorporated herein by reference. Kraft et al. teaches a distributed programming system wherein subtasks are distributed to requesting distributed computers “on demand.” As described in Kraft et al., a coordinating computer segments a program and, then, distributes segments to requesting computers upon occasion of a request. When and how program distribution occurs depends on when enough computers have requested tasks. Further, a slow computer executing a single task may impede program completion. Also, until the last task is assigned, when the program will complete cannot be predicted with any certainty.
Thus, there is a need for reducing computer program execution time, especially for searching, and for making massively parallel computer resources available at a reasonable cost.